(a) Field of the Invention
The present invention relates to a Hybrid Automatic Repeat Request (HARQ) system, and in particular, to an encoding/decoding apparatus of the HARQ system for enhancing error correction performance and packet data transmission efficiency by utilizing Low Density Parity Check (LDPC) codes and by interleaving packets for retransmission.
(b) Description of the Related Art
In communication systems, two basic strategies for dealing with errors have been developed. One is to include only enough redundancy to allow a receiver to deduce that an error has occurred, but not which error, and have it request a retransmission to the sender (Automatic Repeat Request: ARQ). The other way is to include enough redundant information along with each data block sent to enable the receiver to deduce what the transmitted character must have been (Forward Error Correction: FEC). The former uses error-detecting codes, and the latter uses error-correcting codes.
Transmission systems, particularly mobile communication systems, have recently begun to use a combination of ARQ protocols and FEC for high speed data transmission, which is called Hybrid ARQ (HARQ). HARQ compensates for drawbacks of ARQ, i.e., a decrease of throughput due to a large number of retransmissions for low signal-to-noise ratio (SNR), by combining with FEC. In HARQ, turbo codes are used for FEC, and Chase combining and Incremental Redundancy are used for ARQ.
In Evolution Data Only (EV-DO) and High Speed Downlink Packet Access (HSDPA) systems, information is transmitted in packet units encoded by a turbo encoder, and the packet is decoded at the receiver by a turbo decoder using the same encoding/decoding scheme. When the turbo decoder fails to decode the packet, the receiver reports the decoding failure to the transmitter so as to retransmit the packet.
At the receiver, whether or not the packet is successfully decoded is determined by a CRC check on the output of the decoder. When the packet passes the CRC check, the receiver transmits an acknowledgement (ACK) to the transmitter. Otherwise, the receiver transmits a negative acknowledgement (NACK) to the transmitter. The transmitter transmits the next data packet when receiving the ACK. On the other hand, if receiving a NACK, the transmitter retransmits the packet up to a predetermined number of times.
In Chase combining, the transmitter uses the same data packet at both initial transmission and retransmission, and then the receiver combines the initially transmitted packet with the retransmitted packet and performs a decoding operation on the combined packet. The transmitter transmits the next packet when receiving an ACK, and retransmits the previously transmitted packet up to a predetermined number of times when receiving a NACK.
Typically, the transmitter adds redundancy bits to the data to be transmitted so as to allow the decoder to perform correction. In the Incremental Redundancy scheme, the transmitter increments redundancy bits when the packet is retransmitted, i.e., increases a coding rate of retransmission from that of an initial transmission, resulting in enhancement of decoding efficiency at the receiver. Accordingly, the receiver performs the decoding operation using the initially transmitted packet and the retransmitted packet. Chase combining can obtain a diversity gain without an increase of system complexity since the same packet is retransmitted. On the other hand, the Incremental Redundancy increases the system complexity at both the encoder and decoder since the coding rate varies whenever the retransmission is performed again. However, the Incremental Redundancy relatively improves the decoding probability of the transmitted data using the different coding rates. Accordingly, the Incremental Redundancy scheme has been known to show high performance since it provides both diversity gain and coding gain. That is, Incremental Redundancy is superior to Chase combining in view of system performance, while Chase combining is superior to Incremental Redundancy in view of low system complexity.
Two outstanding error correction coding schemes are Block codes and Trellis codes. One Example of Block codes is LDPC codes, and an example of Trellis codes is a convolutional turbo code.
In the case of block codes, the characteristics of the encoder and decoder are determined by a Generating matrix (G) and a Parity Check matrix (H). Basically, the LDPC code is encoded by one encoder and then repeatedly decoded by one decoder so as to show a high performance identical with the turbo code. At that time, the decoder performs decoding by calculating a probability satisfying the relationship (H·C=0) of the parity check bit matrix (H) and a received codeword (C).
In the case of a Trellis code, the encoder encodes a Trellis code using a generator polynomial, and the decoder performs decoding by calculating all of the probabilities of the Trellis codes.
As described above, even though LDPC coding allows the decoder to calculate the relationships (H C=0) of the parity check matrix (H) and the received codeword (C) in parallel, Trellis coding does not support the parallel calculation of the probabilities which increases calculation time.
The turbo code is generated with two convolutional component encoders separated by one interleaver, and is then decoded by two decoders recursively so as to guarantee performance. That is, it is not expected to obtain good performance of the turbo code with only one encoder and one decoder.
FIG. 1 is a conceptual view illustrating a Hybrid Automatic Repeat Request (HARQ) scheme adopted to EV-DO and HSDPA systems.
In FIG. 1, the turbo code encoder consists of first and second convolutional encoders, an interleaver, and a puncturer. The turbo code encoder is a HARQ encoder (The construction of the turbo code encoder is identical when the retransmission function is disabled).
A conventional HARQ technique will be described hereinafter when Chase combining is performed in a ⅓ code rate.
Firstly, the transmitter sends data X, Y1, and Z2, and the receiver performs decoding and CRC. As a result of the CRC, the receiver stores the data and requests retransmission of the data when the decoding has failed such that the transmitter retransmits the X, Y1, and Z2.
When the receiver fails to decode the data again and the current number of retransmission times does not exceed the predetermined number of retransmission times, the receiver requests retransmission again. This process continues until the number of retransmission times reaches the predetermined number of retransmission times.
On the other hand, when the data X, Y1, and Z2 are transmitted in the Incremental Redundancy scheme and the receiver fails to decode the data, the receiver stores the decoding result and requests retransmission of the data. Upon reception of the retransmission request, the transmitter transmits the data X′, Y2, and Z1 and the receiver performs decoding using the currently received data and the previously stored data. When the receiver fails to decode the data again and the current number of retransmission times does not exceed the predetermined number of retransmission times, the receiver requests retransmission again. The transmitter sends the data X, Y1, and Z2 during the odd numbered retransmissions and the data X′, Y2, Z1 during the even numbered retransmissions. This process continues until the number of retransmissions reaches the predetermined number.
The error correction scheme using the turbo codes as described above has drawbacks of an error floor effect in which the system performance is not improved even when increasing signal power at the operation point, and it requires much decoding time due to the sequential decoding operation in units of symbols.